/**
 * @author VernHe
 * @date 2021年07月08日 11:12
 * <p>
 * <p>
 * <p>
 * 有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组nums中。
 * <p>
 * 现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。这里的 i - 1 和 i + 1 代表和i相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
 * <p>
 * 求所能获得硬币的最大数量。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * 输入：nums = [3,1,5,8]
 * 输出：167
 * 解释：
 * nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
 * coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167
 * 示例 2：
 * <p>
 * 输入：nums = [1,5]
 * 输出：10
 */
public class Solution_0312 {

    public int maxCoins(int[] nums) {
        int length = nums.length;
        int newLength = length + 2;
        // 数组首位加1，方便计算
        int[] newArry = new int[newLength];
        newArry[0] = 1;
        newArry[length + 1] = 1;
        // 放入新数组中
        for (int i = 0; i < length; i++) {
            newArry[i + 1] = nums[i];
        }
        // 定义dp数组，dp[i][j] 表示区间(i,j)范围内可以获得的最大金币
        // 假设最后一个被戳爆的是第k个气球，那么，dp[i][j] = dp[i][k] + newArray[i]*newArray[k]*newArray[k] + dp[k][j]
        // 也就是说和他两边区间被戳吧气球获得的最大金币有关
        int[][] dp = new int[newLength][newLength];

        // (i,j)区间的范围从3开始，慢慢递增一直到最大(就是newArray的大小)，范围是[3,newLength]，闭区间
        for (int range = 3; range <= newLength; range++) {
            // 区间从左往右移动，进行初始化，也就i移动的范围是[0,newLength - range]，这是闭区间
            for (int i = 0; i <= newLength - range; i++) {
                // 知道i和rang可以确定j
                int j = i + range - 1;
                // 找出(i,j)这个区间内的最大值，就是依次试着去戳破，然后记录最大值
                int maxValue = 0;
                // 在(i,j)区间内尝试依次去戳破气球，并记录每次获得的金币
                for (int k = i + 1; k < j; k++) {
                    // 区间(i,k)区间内戳气球能获得的最大金币
                    int leftRangeValu = dp[i][k];
                    // 区间(k,j)区间内戳气球能获得的最大金币
                    int rightRangeValue = dp[k][j];
                    maxValue = Math.max(maxValue, leftRangeValu + newArry[i] * newArry[k] * newArry[j] + rightRangeValue);
                }
                // 将最大值保存到dp数组中
                dp[i][j] = maxValue;
            }
        }
        return dp[0][length + 1];
    }
}
